# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def print_list(head):
    current = head
    while current is not None:
        print(current.val, end=' ')
        current = current.next
class Solution(object):
    def mergeTwoLists(self, list1, list2):
        """
        :type list1: Optional[ListNode]
        :type list2: Optional[ListNode]
        :rtype: Optional[ListNode]
        """
        # 递归
        # if list1 is None:
        #     return list2
        # elif list2 is None:
        #     return list1
        # elif list1.val < list2.val:
        #     # 如果list1的当前节点值小于list2的当前节点值，
        #     # 则新的头节点是list1的当前节点，并递归合并list1的下一个节点和list2
        #     list1.next = self.mergeTwoLists(list1.next, list2)
        #     return list1
        # else:
        #     # 如果list1的当前节点值大于等于list2的当前节点值，
        #     # 则新的头节点是list2的当前节点，并递归合并list1和list2的下一个节点
        #     list2.next = self.mergeTwoLists(list1, list2.next)
        #     return list2
        # 迭代
        result = ListNode(-1)
        current = result
        while list1 and list2:
            if list1.val <= list2.val:
                current.next = list1
                list1 = list1.next
            else:
                current.next = list2
                list2 = list2.next
            current = current.next
        current.next = list1 or list2
        return result.next
l1 = ListNode(1)
l1.next = ListNode(2)
l1.next.next = ListNode(4)
l2 = ListNode(1)
l2.next = ListNode(3)
l2.next.next = ListNode(4)
example = Solution()
print_list(example.mergeTwoLists(l1,l2))